package a11_单调栈;

import java.util.Stack;

/**
 * <p>
 * a05_柱状图中最大的矩形复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/3/10
 */
public class a05_柱状图中最大的矩形复习1 {
    public int largestRectangleArea(int[] heights) {
        int[] nums = new int[heights.length+2];
        System.arraycopy(heights, 0, nums, 1, heights.length);
        int result = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 1; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i])  {
                Integer pop = stack.pop();
                if (!stack.isEmpty()) {
                    int height = nums[pop];
                    int width = i - stack.peek() - 1;
                    result = Math.max(result, height * width);
                }
            }
            stack.push(i);
        }
        return result;
    }
}
